package com.springboot.test.sort;

import java.util.Arrays;

/**
 *  桶排序   计数排序的升级，计数排序一个位置只记相同的元素，桶是记录一定范围内的数
 *      时间复杂度  O(N+M+N(logN-logM))
 *      稳定性     稳定
 */
public class BucketSort {
    /**
     *  桶大小
     */
    private static final int BUCKET_SIZE = 10;

    public static void main(String[] args) {

        int[] arr = {2,35,65,123,6,7,12,1};

        System.out.println(Arrays.toString(arr));

        sort(arr);

        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr){
        // 最小和最大元素
        int min = arr[0], max = arr[0];

        for (int i = 0; i < arr.length; i++) {
            if(arr[i] < min){
                min = arr[i];
            }
            if(arr[i] > max){
                max = arr[i];
            }
        }
        // 确定桶个数
        int bucketCount = (max - min) / BUCKET_SIZE + 1;
        // 初始化桶
        int[][] buckets = new int[bucketCount][0];
        // 将排序数组元素分布到桶中
        for (int i = 0; i < arr.length; i++) {
            int bucketIndex = (arr[i] - min) / BUCKET_SIZE;
            buckets[bucketIndex] = arrAppend(buckets[bucketIndex], arr[i]);
        }
        // 对桶内进行排序
        for (int i = 0, k = 0; i < bucketCount; i++) {
            if(buckets[i].length == 0){
                continue;
            }
            buckets[i] = FastSort.sort(buckets[i], 0, buckets[i].length - 1);
            for (int j = 0; j < buckets[i].length; j++) {
                arr[k++] = buckets[i][j];
            }
        }

    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private static int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}
